The present invention relates generally to image processing. It relates more particularly to manipulation of digitized images, such as rotating, cropping, and zooming, that is performed prior to printing or displaying the image in a final form.
Storage of pictures and images in computer-readable form is commonplace. Scanners are used to digitize printed pictures or artwork. In digital cameras, flash memory cards replace film as the medium for capturing and storing photographs. The data files created by scanners, digital cameras, and the like can be stored and transmitted; for example, by e-mail, or by incorporating them into web pages for the internet.
Software programs translate data files representing images into a form which can be displayed on devices such as a computer monitor or the LCD viewfinder within a digital camera, and subsequently printed in a hard copy form.
In order for digitized images to be widely exchanged and accessed, the image information in the data file must be stored in an agreed-to format. Many such formats have been developed. Formats for still pictures include Bitmap, GIF, TIFF, and JFIF; formats for moving pictures include MPEG and AVI.
It takes a large amount of digital memory to store a high resolution digitized photograph consisting of hundreds of thousands of individual picture elements known as pixels. Such large amounts of storage are necessary because each pixel in the digitized photograph represents the absence or presence of an image element as well as supporting information such as the color and brightness of that element of the image when present. It is very common for digitized images to be stored in a row-and-column matrix format of at least 1024 pixels in one direction (for instance, horizontal) by 768 pixels in the other direction (eg. vertical), resulting in a total of 786,432 pixels for the image. If the image is in color, multiple sets of information, called color channels, are needed to record both the brightness and the color of the pixel. One way of storing color information, known as RGB format, uses separate sets for the brightness of red, green, and blue, which when mixed together produce the correct color of the pixel. Another way, known as YCbCr (or YCC) format, stores brightness (or luminance) information in one set, and uses two sets to store color (chrominance) information.
Computer memory is structured logically as a one-dimensional block of consecutive storage locations, each of which has an address. The two-dimensional image information is stored in this one-dimensional memory in a order specified by the image format. One common order is to store the pixels in row order, from left to right beginning with the top row of the image, then the second from the top row from left to right, and repeating this sequence until the entire image has been stored.
When digitized image data is stored in RGB or YCC format, the amount of storage required to hold the information for a single pixel is the same for all pixels, typically about 8 to 12 bits of information. Because the amount of storage per pixel is fixed, and because the order in which pixels are stored is known, a computer program can easily calculate the location in memory of any individual pixel. Sometimes rectangular sets of pixels in the digitized image is grouped into an image area. Since the number of vertical and horizontal pixels per image area is fixed, the size of all image areas is the same, and thus the location in memory of any individual image area can similarly be easily calculated. When the digitized image is to be manipulated, for example by rotating, cropping, or zooming it, specific image areas need to be located in a non-sequential order. Because the location of image areas can be easily calculated, the image areas can be obtained from memory quickly and efficiently.
However, storing a digitized image in the type of format described has the disadvantage of requiring a large amount of memory. The larger the amount of memory required per image, the fewer the number of images that can be stored on a memory device of a given storage capacity, such as a disk drive or the flash memory card in a digital camera. To increase the number of files that can be stored on a given memory device, many systems encode the digitized image to compress the image data into a smaller size before storing it in memory. Compression transforms the data so as to reduce the amount of memory required to hold the digitized image. One commonly used compression technique, known as variable length encoding or entropy encoding, results in the image areas no longer being the same size. As a result, the location of individual image areas can no longer be calculated, and image areas cannot be accessed in a non-sequential fashion. In order to find a desired image area, the image must be decoded sequentially bit-by-bit from the start of the image until the desired image area is located.
Several techniques for accessing individual image areas in a digitized image stored using variable length encoding are known to those skilled in the art. One prior art method decompresses the entire image file area by area into a buffer memory, expanding the image areas back to a fixed size so that the location of areas can be easily calculated. A drawback to this method is that a buffer memory large enough to hold the entire image in uncompressed format is required. Adding a memory element or increasing the size of an existing memory element to accommodate large, uncompressed image files can significantly increase the cost of a printer, digital camera, or other type of computer peripheral that performs image manipulations on compressed files.
Another prior art method scans the file sequentially, counting and discarding areas until the desired one is encountered. This method does not require a large buffer, but instead requires a disproportionately large amount of processing time because this method is repeated, starting from the beginning of the file, for each image area to be processed. In order to complete the image manipulation in an acceptable amount of time, a more powerful processor than otherwise needed may be required, which can also significantly increase the cost of the product.
Yet another prior art method stores location information for the image areas in the data file, along with the image areas themselves, prior to compression. However, including this additional information in the image file makes the size larger, and more importantly results in a custom image file format that is no longer compatible with industry standards. This prevents a device using this method from manipulating files stored in a standard file format, and thus inhibits exchange of digitized images with others.
From the foregoing, it is apparent that there is still a need for a way to randomly access individual areas of image information stored in a variable length encoded format without requiring a large buffer memory, excessive processing time or power, or use of a non-standard image file format.
In a preferred embodiment, an image processing apparatus includes a prescanner that sequentially detects individual ones of a plurality of encoded image areas embedded within a data bitstream of digital information and a decoder that decodes at least some of the detected ones of the plurality of encoded image areas that have been temporarily stored. In accordance with the novel processing method of the present invention, the prescanner stores only locating information relative to a first encoded image area word for each of the image areas in the digital image to be processed for image manipulation purposes. The temporarily stored location information is selectively retrieved by the decoder in a non-sequential manner and then decoded for image manipulation purposes in accordance with conventional image manipulation techniques. In short, the novel method locates and decodes only those image areas of interest relative to an image manipulation process. Types of image manipulation include rotating, cropping, or zooming the image. For each color channel in the digitized image, coefficients which assist in decoding image areas when they are accessed non-sequentially may optionally be stored along with the location information. Image areas for which location information is not stored may be accessed efficiently by non-sequentially accessing a prior image area for which location information is stored, then sequentially accessing subsequent image areas until the area of interest is located.
In another preferred embodiment of the present invention, an image processing system includes an image processing apparatus that is coupled between a data bitstream source and an output viewing arrangement. The image processing apparatus sequentially scans the bitstream provided by the data bitstream source in order to locate data indicative of compressed image areas within a digitized image displayable on the output viewing arrangement. The image processing apparatus temporarily stores location information identifying the location of each image area within the data bitstream and subsequently retrieves selected ones of the stored location information to fully decode the image data associated with the retrieved information for displaying or printing a manipulated image via the output viewing arrangement. The image processing apparatus includes an image restructuring device which manipulates the decoded image areas, under the control of an image processing executive which designates the image areas to be decoded and the image manipulation operation to be performed.
Other aspects and advantages of the present invention will become apparent from the following detailed description, taken in conjunction with the accompanying drawings, illustrating by way of example the principles of the invention. The claims alone, not the preceding summary or the following detailed description, define the invention.